// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-28 16:27
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

public class repeatRemoveDulpical {
    // 贪心 + 单调栈
    public String removeDuplicateLetters(String s) {
        boolean[] vis = new boolean[26]; // 字母都是小写
        int[] nums = new int[26];// 用于记录字符串中字符出现的次数
        int n = s.length();
        // 数组初始化
        for (int i = 0; i < n; i++) {
            nums[s.charAt(i) - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (!vis[c - 'a']) {
                // 当前字符还没有出现过
                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > c) {
                    // 找到最小的s[i]>s[i+1]并且进行重复操作
                    if (nums[sb.charAt(sb.length() - 1) - 'a'] > 0) { // 栈顶元素是在字符串中是重复元素
                        vis[sb.charAt(sb.length() - 1)-'a'] = false; // 当前字符位置不对
                        sb.deleteCharAt(sb.length() - 1);// 删除栈顶元素
                    } else {
                        break;
                    }
                }
                sb.append(c);
                vis[c - 'a'] = true;
            }
            nums[c - 'a'] -= 1;//元素入栈
        }
        return sb.toString();
    }
}
